class Solution {
public:
    unordered_set<string> s;
    int openLock(vector<string>& deadends, string target) {
        for (auto& x : deadends) s.insert(x);
        queue<pair<string, int>> que;
        if (s.find("0000") != s.end()) return -1;
        que.push(pair<string, int>("0000", 0));
        while (!que.empty())
        {
            pair<string, int> temp = que.front();
            que.pop();
            if (temp.first == target) return temp.second;
            for (int i = 0; i < 4; i++)
            {
                int c = temp.first[i] - '0';
                string ne1 = temp.first, ne2 = temp.first;
                ne1[i] = (c + 1) % 10 + '0';
                ne2[i] = (c + 9) % 10 + '0';
                if (s.find(ne1) == s.end())
                {
                    s.insert(ne1);
                    que.push(pair<string, int>(ne1, temp.second + 1));
                }
                if (s.find(ne2) == s.end())
                {
                    s.insert(ne2);
                    que.push(pair<string, int>(ne2, temp.second + 1));
                }
            }
        }
        return -1;
    }
};